package demo1;//https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId=128&tqId=33768&ru=/exam/oj
//最大差值

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param n int整型 
     * @return int整型
     */
    public static int getDis1 (int[] A, int n) {
        // write code here
        int ret = 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = A[0];
        g[n-1] = A[n-1];

        for(int i = 1, j = n-2; i<n; i++, j--) {
            f[i] = Math.min(f[i-1], A[i]);
            g[j] = Math.max(g[j+1], A[j]);
        }

        for(int i = 0; i<n; i++) {
            ret = Math.max(ret, g[i] - f[i]);
        }
        return ret;
    }

    //优化版本2
    public static int getDis2 (int[] A, int n) {
        // write code here
        int ret = 0;
        int[] f = new int[n];
        f[0] = A[0];

        for(int i = 1; i<n; i++) {
            f[i] = Math.min(f[i-1], A[i]);
        }

        for(int i = 0; i<n; i++) {
            ret = Math.max(ret, A[i] - f[i]);
        }
        return ret;
    }

    //优化版本3
    public static int getDis (int[] A, int n) {
        // write code here
        int ret = 0;
        int minPre = A[0];

        for(int i = 1; i<n; i++) {
            minPre = Math.min(A[i], minPre);
            ret = Math.max(ret, A[i] - minPre);
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = {5,6};
        int ret = getDis(arr, 2);
        System.out.println(ret);
    }
}

/*

  1 2 3 6 7 8
  f[i]: 下标为 0-i 之间的最小值
  g[i]: 下标为 i-n 之间的最大值

 */